﻿//#include <iostream>
//using namespace std;
//int main()
//{
//    int n = 0;
//    cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        int a = 0, b = 0, c = 0, count = 0;
//        cin >> a >> b >> c;
//        while (a - 1 >= 0 && b - 1 >= 0 && c - 1 >= 0)
//        {
//            count += 2;
//            a--;
//            b--;
//            c--;
//        }
//        if (b > 1)
//        {
//            count += b - 1;
//        }
//        cout << count << endl;
//    }
//    return 0;
//}

//class Solution 
//{
//public:
//    int rotApple(vector<vector<int>>& grid) 
//    {
//        int minit = 0;
//        int n = 2;
//        while (1)
//        {
//            int m = n;
//            for (int i = 0; i < grid.size(); i++)
//            {
//                for (int j = 0; j < grid[i].size(); j++)
//                {
//                    if (grid[i][j] == m)
//                    {
//                        //上
//                        if (i != 0 && grid[i - 1][j] == 1)
//                        {
//                            grid[i - 1][j] += m;
//                            n = grid[i - 1][j];
//                        }
//                        //下
//                        if (i != grid.size() - 1 && grid[i + 1][j] == 1)
//                        {
//                            grid[i + 1][j] += m;
//                            n = grid[i + 1][j];
//                        }
//                        //左
//                        if (j != 0 && grid[i][j - 1] == 1)
//                        {
//                            grid[i][j - 1] += m;
//                            n = grid[i][j - 1];
//                        }
//                        //右
//                        if (j != grid[i].size() - 1 && grid[i][j + 1] == 1)
//                        {
//                            grid[i][j + 1] += m;
//                            n = grid[i][j + 1];
//                        }
//                    }
//                }
//            }
//            if (n == m)
//            {
//                for (int i = 0; i < grid.size(); i++)
//                {
//                    for (int j = 0; j < grid[i].size(); j++)
//                    {
//                        if (grid[i][j] == 1)
//                        {
//                            return -1;
//                        }
//                    }
//                }
//                return minit;
//            }
//            minit++;
//        }
//    }
//};

//class Solution 
//{
//public:
//    int LastRemaining_Solution(int n, int m)
//    {
//        vector<int> v;
//        for (int i = 0; i < n; i++)
//        {
//            v.push_back(i);
//        }
//        vector<int>::iterator it = v.begin();
//        while (v.size() != 1)
//        {
//            int i = 0;
//            while (i != m - 1)
//            {
//                it++;
//                if (it == v.end())
//                {
//                    it = v.begin();
//                }
//                i++;
//            }
//            it = v.erase(it);
//            if (it == v.end())
//            {
//                it = v.begin();
//            }
//        }
//        return v.front();
//    }
//};



//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     * 计算两个数之和
//     * @param s string字符串 表示第一个整数
//     * @param t string字符串 表示第二个整数
//     * @return string字符串
//     */
//    string solve(string s, string t) {
//        if (s.empty())
//        {
//            return t;
//        }
//        if (t.empty())
//        {
//            return s;
//        }
//        string str;
//        int MinLength = s.size() < t.size() ? s.size() : t.size();
//        for (int i = 1; i <= MinLength; i++)
//        {
//            int x = 0;
//            char c = s[s.size() - i] + t[t.size() - i] - 48;
//            str.push_back(c);
//        }
//        while (s.size() > t.size() && MinLength < s.size())
//        {
//            MinLength++;
//            str.push_back(s[s.size() - MinLength]);
//        }
//        while (s.size() < t.size() && MinLength < t.size())
//        {
//            MinLength++;
//            str.push_back(t[t.size() - MinLength]);
//        }
//        //进位
//        for (int i = 0; i < str.size(); i++)
//        {
//            if (str[i] > '9')
//            {
//                str[i] -= 10;
//                if (i != str.size() - 1)
//                {
//                    str[i + 1] += 1;
//                }
//                else
//                {
//                    str.push_back('1');
//                }
//            }
//        }
//        reverse(str.begin(), str.end());
//        return str;
//    }
//};


///**
// * struct ListNode {
// *	int val;
// *	struct ListNode *next;
// *	ListNode(int x) : val(x), next(nullptr) {}
// * };
// */
//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     * @param head1 ListNode类
//     * @param head2 ListNode类
//     * @return ListNode类
//     */
//    ListNode* addInList(ListNode* head1, ListNode* head2) {
//        //修改链表链接
//        ListNode* p1 = head1;
//        ListNode* last1 = head1;
//        ListNode* next1 = p1->next;
//        p1->next = nullptr;
//        while (next1)
//        {
//            p1 = next1;
//            next1 = next1->next;
//            p1->next = last1;
//            last1 = p1;
//        }
//        ListNode* p2 = head2;
//        ListNode* last2 = head2;
//        ListNode* next2 = p2->next;
//        p2->next = nullptr;
//        while (next2)
//        {
//            p2 = next2;
//            next2 = next2->next;
//            p2->next = last2;
//            last2 = p2;
//        }
//        //存入容器vector中
//        vector<int> v;
//        int x = 0;
//        while (p1 && p2)
//        {
//            if (p1->val + p2->val + x > 9)
//            {
//                v.push_back(p1->val + p2->val + x - 10);
//                x = 1;
//            }
//            else
//            {
//                v.push_back(p1->val + p2->val + x);
//                x = 0;
//            }
//            p1 = p1->next;
//            p2 = p2->next;
//        }
//        while (p1 == nullptr && p2)
//        {
//            if (p2->val + x > 9)
//            {
//                v.push_back(p2->val + x - 10);
//                x = 1;
//            }
//            else
//            {
//                v.push_back(p2->val + x);
//                x = 0;
//            }
//            p2 = p2->next;
//        }
//        while (p2 == nullptr && p1)
//        {
//            if (p1->val + x > 9)
//            {
//                v.push_back(p1->val + x - 10);
//                x = 1;
//            }
//            else
//            {
//                v.push_back(p1->val + x);
//                x = 0;
//            }
//            p1 = p1->next;
//        }
//        if (x == 1)
//        {
//            v.push_back(1);
//        }
//        //将容器vector中的数据建立链表并返回
//        ListNode* head = new ListNode(v[v.size() - 1]);
//        ListNode* p = head;
//        for (int i = v.size() - 2; i >= 0; i--)
//        {
//            ListNode* next = new ListNode(v[i]);
//            p->next = next;
//            p = next;
//        }
//        return head;
//    }
//};


//class Solution
//{
//public:
//    string solve(string s, string t)
//    {
//        if (s.empty())
//        {
//            return t;
//        }
//        if (t.empty())
//        {
//            return s;
//        }
//        if (s == "0" || t == "0")
//        {
//            return "0";
//        }
//        string str(t);
//        string sp(s.size(), '0');
//        sp[s.size() - 1] = '1';
//        while (sp != s)
//        {
//            if (s[s.size() - 1] == '0')
//            {
//                int i = s.size() - 2;
//                while (s[i] == '0')
//                {
//                    s[i] = '9';
//                    i--;
//                }
//                s[i] -= 1;
//                s[s.size() - 1] = '9' + 1;
//            }
//            //str与t加法操作
//            int x = 0; //进位数
//            for (int i = 1; i <= t.size(); i++)
//            {
//                str[str.size() - i] += x + t[t.size() - i] - 48;
//                if (str[str.size() - i] > '9')
//                {
//                    str[str.size() - i] -= 10;
//                    x = 1;
//                }
//                else
//                {
//                    x = 0;
//                }
//            }
//            if (x == 1)
//            {
//                for (int i = str.size() - t.size() - 1; i >= 0; i--)
//                {
//                    if (str[i] + x > '9')
//                    {
//                        str[i] = '0';
//                        x = 1;
//                    }
//                    else
//                    {
//                        str[i] += x;
//                        x = 0;
//                        break;
//                    }
//                }
//                if (x == 1)
//                {
//                    str.insert(str.begin(), '1');
//                }
//            }
//            s[s.size() - 1] -= 1;
//        }
//        return str;
//    }
//};

//#include <iostream>
//#include <string>
//#include <map>
//using namespace std;
//
//int main()
//{
//    string str;
//    map<int, string> m;
//    cin >> str;
//    for (int i = 0; i < str.size(); i++)
//    {
//        int count = 0;
//        string s;
//        while (str[i] >= '0' && str[i] <= '9')
//        {
//            count++;
//            s.push_back(str[i]);
//            i++;
//        }
//        if (count)
//        {
//            m[count] = s;
//        }
//    }
//    int max = 0;
//    for (map<int, string>::iterator it = m.begin(); it != m.end(); it++)
//    {
//        if (it->first > max)
//        {
//            max = it->first;
//        }
//    }
//    cout << m[max] << endl;
//    return 0;
//}



//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main()
//{
//    int t = 0;
//    cin >> t;
//    for (int i = 0; i < t; i++)
//    {
//        vector<int> v(6);
//        for (int j = 0; j < 6; j++)
//        {
//            cin >> v[j];
//        }
//        int count = 0;
//        for (int a = 0; a <= 3; a++)
//        {
//            for (int b = a + 1; b <= 4; b++)
//            {
//                for (int c = b + 1; c <= 5; c++)
//                {
//                    if (v[a] + v[b] > v[c] && v[a] + v[c] > v[b] && v[b] + v[c] > v[a])
//                    {
//                        int x = 0, y = 0, z = 0;
//                        for (int k = 0; k < 6; k++)
//                        {
//                            if (x == 0 && k != a && k != b && k != c)
//                            {
//                                x = v[k];
//                            }
//                            else if (y == 0 && k != a && k != b && k != c)
//                            {
//                                y = v[k];
//                            }
//                            else if (z == 0 && k != a && k != b && k != c)
//                            {
//                                z = v[k];
//                            }
//                        }
//                        if (x + y > z && x + z > y && y + z > x)
//                        {
//                            count = 1;
//                            a = 3;
//                            b = 4;
//                            c = 5;
//                            cout << "Yes" << endl;
//                        }
//                    }
//                }
//            }
//        }
//        if (count == 0)
//        {
//            cout << "No" << endl;
//        }
//    }
//    return 0;
//}
